<!DOCTYPE HTML>
<html lang="zh" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using https://github.com/wa-lang/wabook -->
        <meta charset="UTF-8">
        <title>请求路由 - Go语言高级编程</title>
        <!-- Custom HTML head -->
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="../favicon.svg">
        <link rel="shortcut icon" href="../favicon.png">
        <link rel="stylesheet" href="../static/wabook/css/variables.css">
        <link rel="stylesheet" href="../static/wabook/css/general.css">
        <link rel="stylesheet" href="../static/wabook/css/chrome.css">
        <link rel="stylesheet" href="../static/wabook/css/print.css" media="print">
        <!-- Fonts -->
        <link rel="stylesheet" href="../static/wabook/FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="../static/wabook/fonts/fonts.css">
        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="../static/wabook/highlight.css">
        <link rel="stylesheet" href="../static/wabook/tomorrow-night.css">
        <link rel="stylesheet" href="../static/wabook/ayu-highlight.css">

        <!-- Custom theme stylesheets -->
    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "../";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('wabook-theme');
                var sidebar = localStorage.getItem('wabook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('wabook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('wabook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('wabook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('wabook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter">
  <li class="chapter-item expanded ">
    <a href="../index.html" >Go语言高级编程</a>
  </li>
  <li class="chapter-item expanded ">
    <a href="../preface.html" >前言</a>
  </li>
  <li class="chapter-item expanded ">
    <a href="../ch1-basic\readme.html" ><strong aria-hidden="true">1.</strong> 语言基础</a>
  </li>
  <ol class="section">
    <li class="chapter-item expanded ">
      <a href="../ch1-basic\ch1-01-genesis.html" ><strong aria-hidden="true">1.1.</strong> Go语言创世纪</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch1-basic\ch1-02-hello-revolution.html" ><strong aria-hidden="true">1.2.</strong> Hello, World 的革命</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch1-basic\ch1-03-array-string-and-slice.html" ><strong aria-hidden="true">1.3.</strong> 数组、字符串和切片</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch1-basic\ch1-04-func-method-interface.html" ><strong aria-hidden="true">1.4.</strong> 函数、方法和接口</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch1-basic\ch1-05-mem.html" ><strong aria-hidden="true">1.5.</strong> 面向并发的内存模型</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch1-basic\ch1-06-goroutine.html" ><strong aria-hidden="true">1.6.</strong> 常见的并发模式</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch1-basic\ch1-07-error-and-panic.html" ><strong aria-hidden="true">1.7.</strong> 错误和异常</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch1-basic\ch1-08-ext.html" ><strong aria-hidden="true">1.8.</strong> 补充说明</a>
    </li>
  </ol>
  <li class="chapter-item expanded ">
    <a href="../ch2-cgo\readme.html" ><strong aria-hidden="true">2.</strong> CGO编程</a>
  </li>
  <ol class="section">
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-01-hello-cgo.html" ><strong aria-hidden="true">2.1.</strong> 快速入门</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-02-basic.html" ><strong aria-hidden="true">2.2.</strong> CGO基础</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-03-cgo-types.html" ><strong aria-hidden="true">2.3.</strong> 类型转换</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-04-func.html" ><strong aria-hidden="true">2.4.</strong> 函数调用</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-05-internal.html" ><strong aria-hidden="true">2.5.</strong> 内部机制</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-06-qsort.html" ><strong aria-hidden="true">2.6.</strong> 实战: 封装qsort</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-07-memory.html" ><strong aria-hidden="true">2.7.</strong> CGO内存模型</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-08-class.html" ><strong aria-hidden="true">2.8.</strong> C++类包装</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-09-static-shared-lib.html" ><strong aria-hidden="true">2.9.</strong> 静态库和动态库</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-10-link.html" ><strong aria-hidden="true">2.10.</strong> 编译和链接参数</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch2-cgo\ch2-11-ext.html" ><strong aria-hidden="true">2.11.</strong> 补充说明</a>
    </li>
  </ol>
  <li class="chapter-item expanded ">
    <a href="../ch3-asm\readme.html" ><strong aria-hidden="true">3.</strong> 汇编语言</a>
  </li>
  <ol class="section">
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-01-basic.html" ><strong aria-hidden="true">3.1.</strong> 快速入门</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-02-arch.html" ><strong aria-hidden="true">3.2.</strong> 计算机结构</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-03-const-and-var.html" ><strong aria-hidden="true">3.3.</strong> 常量和全局变量</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-04-func.html" ><strong aria-hidden="true">3.4.</strong> 函数</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-05-control-flow.html" ><strong aria-hidden="true">3.5.</strong> 控制流</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-06-func-again.html" ><strong aria-hidden="true">3.6.</strong> 再论函数</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-07-hack-asm.html" ><strong aria-hidden="true">3.7.</strong> 汇编语言的威力</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-08-goroutine-id.html" ><strong aria-hidden="true">3.8.</strong> 例子：Goroutine ID</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-09-debug.html" ><strong aria-hidden="true">3.9.</strong> Delve调试器</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch3-asm\ch3-10-ext.html" ><strong aria-hidden="true">3.10.</strong> 补充说明</a>
    </li>
  </ol>
  <li class="chapter-item expanded ">
    <a href="../ch4-rpc\readme.html" ><strong aria-hidden="true">4.</strong> 第4章 RPC和Protobuf</a>
  </li>
  <ol class="section">
    <li class="chapter-item expanded ">
      <a href="../ch4-rpc\ch4-01-rpc-intro.html" ><strong aria-hidden="true">4.1.</strong> RPC入门</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch4-rpc\ch4-02-pb-intro.html" ><strong aria-hidden="true">4.2.</strong> Protobuf</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch4-rpc\ch4-03-netrpc-hack.html" ><strong aria-hidden="true">4.3.</strong> 玩转RPC</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch4-rpc\ch4-04-grpc.html" ><strong aria-hidden="true">4.4.</strong> gRPC入门</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch4-rpc\ch4-05-grpc-hack.html" ><strong aria-hidden="true">4.5.</strong> gRPC进阶</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch4-rpc\ch4-06-grpc-ext.html" ><strong aria-hidden="true">4.6.</strong> gRPC和Protobuf扩展</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch4-rpc\ch4-07-pbgo.html" ><strong aria-hidden="true">4.7.</strong> pbgo: 基于Protobuf的框架</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch4-rpc\ch4-08-grpcurl.html" ><strong aria-hidden="true">4.8.</strong> grpcurl工具</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch4-rpc\ch4-09-ext.html" ><strong aria-hidden="true">4.9.</strong> 补充说明</a>
    </li>
  </ol>
  <li class="chapter-item expanded ">
    <a href="../ch5-web\readme.html" ><strong aria-hidden="true">5.</strong> Go和Web</a>
  </li>
  <ol class="section">
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-01-introduction.html" ><strong aria-hidden="true">5.1.</strong> Web开发简介</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-02-router.html" class="active"><strong aria-hidden="true">5.2.</strong> 请求路由</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-03-middleware.html" ><strong aria-hidden="true">5.3.</strong> 中间件</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-04-validator.html" ><strong aria-hidden="true">5.4.</strong> 请求校验</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-05-database.html" ><strong aria-hidden="true">5.5.</strong> 和数据库打交道</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-06-ratelimit.html" ><strong aria-hidden="true">5.6.</strong> 服务流量限制</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-07-layout-of-web-project.html" ><strong aria-hidden="true">5.7.</strong> 大型Web项目分层</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-08-interface-and-web.html" ><strong aria-hidden="true">5.8.</strong> 接口和表驱动开发</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-09-gated-launch.html" ><strong aria-hidden="true">5.9.</strong> 灰度发布和A/B测试</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch5-web\ch5-10-ext.html" ><strong aria-hidden="true">5.10.</strong> 补充说明</a>
    </li>
  </ol>
  <li class="chapter-item expanded ">
    <a href="../ch6-cloud\readme.html" ><strong aria-hidden="true">6.</strong> 分布式系统</a>
  </li>
  <ol class="section">
    <li class="chapter-item expanded ">
      <a href="../ch6-cloud\ch6-01-dist-id.html" ><strong aria-hidden="true">6.1.</strong> 分布式 id 生成器</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch6-cloud\ch6-02-lock.html" ><strong aria-hidden="true">6.2.</strong> 分布式锁</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch6-cloud\ch6-03-delay-job.html" ><strong aria-hidden="true">6.3.</strong> 延时任务系统</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch6-cloud\ch6-04-search-engine.html" ><strong aria-hidden="true">6.4.</strong> 分布式搜索引擎</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch6-cloud\ch6-05-load-balance.html" ><strong aria-hidden="true">6.5.</strong> 负载均衡</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch6-cloud\ch6-06-config.html" ><strong aria-hidden="true">6.6.</strong> 分布式配置管理</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch6-cloud\ch6-07-crawler.html" ><strong aria-hidden="true">6.7.</strong> 分布式爬虫</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../ch6-cloud\ch6-08-ext.html" ><strong aria-hidden="true">6.8.</strong> 补充说明</a>
    </li>
  </ol>
  <li class="chapter-item expanded ">
    <a href="../appendix\readme.html" ><strong aria-hidden="true">7.</strong> 附录</a>
  </li>
  <ol class="section">
    <li class="chapter-item expanded ">
      <a href="../appendix\appendix-a-trap.html" ><strong aria-hidden="true">7.1.</strong> 附录A: Go语言常见坑</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../appendix\appendix-b-gems.html" ><strong aria-hidden="true">7.2.</strong> 附录B: 有趣的代码片段</a>
    </li>
    <li class="chapter-item expanded ">
      <a href="../appendix\appendix-c-author.html" ><strong aria-hidden="true">7.3.</strong> 附录C: 作者简介</a>
    </li>
  </ol>
</ol>

            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                    </div>

                    <h1 class="menu-title"><a href="../index.html">Go语言高级编程</a></h1>

                    <div class="right-buttons">
                        <a href="https://github.com/chai2010/advanced-go-programming-book" title="Git repository" aria-label="Git repository">
                            <i id="git-repository-button" class="fa fa-github"></i>
                        </a>
                        <a href="https://github.com/chai2010/advanced-go-programming-book/edit/master/ch5-web\ch5-02-router.md" title="Suggest an edit" aria-label="Suggest an edit">
                            <i id="git-edit-button" class="fa fa-edit"></i>
                        </a>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <!-- Page table of contents -->
                    <div class="sidetoc"><nav class="pagetoc"></nav></div>

                    <main>
                        <ul dir="auto"><li><em>凹语言(Go实现, 面向WASM设计): <a href="https://github.com/wa-lang/wa">https://github.com/wa-lang/wa</a></em></li><li><em>WaBook(Go语言实现的MD电子书构建工具): <a href="https://github.com/wa-lang/wabook">https://github.com/wa-lang/wabook</a></em></li></ul><hr>

                        <h1>5.2 router 请求路由</h1>
<p>在常见的 Web 框架中，router 是必备的组件。Go 语言圈子里 router 也时常被称为 <code>http</code> 的 multiplexer。在上一节中我们通过对 Burrow 代码的简单学习，已经知道如何用 <code>http</code> 标准库中内置的 mux 来完成简单的路由功能了。如果开发 Web 系统对路径中带参数没什么兴趣的话，用 <code>http</code> 标准库中的 <code>mux</code> 就可以。</p>
<p>RESTful 是几年前刮起的 API 设计风潮，在 RESTful 中除了 GET 和 POST 之外，还使用了 HTTP 协议定义的几种其它的标准化语义。具体包括：</p>
<pre><code class="language-go">const (
	MethodGet     = &quot;GET&quot;
	MethodHead    = &quot;HEAD&quot;
	MethodPost    = &quot;POST&quot;
	MethodPut     = &quot;PUT&quot;
	MethodPatch   = &quot;PATCH&quot; // RFC 5789
	MethodDelete  = &quot;DELETE&quot;
	MethodConnect = &quot;CONNECT&quot;
	MethodOptions = &quot;OPTIONS&quot;
	MethodTrace   = &quot;TRACE&quot;
)
</code></pre>
<p>来看看 RESTful 中常见的请求路径：</p>
<pre><code class="language-shell">GET /repos/:owner/:repo/comments/:id/reactions

POST /projects/:project_id/columns

PUT /user/starred/:owner/:repo

DELETE /user/starred/:owner/:repo
</code></pre>
<p>相信聪明的你已经猜出来了，这是 Github 官方文档中挑出来的几个 API 设计。RESTful 风格的 API 重度依赖请求路径。会将很多参数放在请求 URI 中。除此之外还会使用很多并不那么常见的 HTTP 状态码，不过本节只讨论路由，所以先略过不谈。</p>
<p>如果我们的系统也想要这样的 URI 设计，使用标准库的 <code>mux</code> 显然就力不从心了。</p>
<h2>5.2.1 httprouter</h2>
<p>较流行的开源 go Web 框架大多使用 httprouter，或是基于 httprouter 的变种对路由进行支持。前面提到的 Github 的参数式路由在 httprouter 中都是可以支持的。</p>
<p>因为 httprouter 中使用的是显式匹配，所以在设计路由的时候需要规避一些会导致路由冲突的情况，例如：</p>
<pre><code>conflict:
GET /user/info/:name
GET /user/:id

no conflict:
GET /user/info/:name
POST /user/:id
</code></pre>
<p>简单来讲的话，如果两个路由拥有一致的 http 方法 (指 <code>GET</code>、<code>POST</code>、<code>PUT</code>、<code>DELETE</code>) 和请求路径前缀，且在某个位置出现了 A 路由是 wildcard（指 <code>:id</code> 这种形式）参数，B 路由则是普通字符串，那么就会发生路由冲突。路由冲突会在初始化阶段直接 panic：</p>
<pre><code class="language-shell">panic: wildcard route ':id' conflicts with existing children in path '/user/:id'

goroutine 1 [running]:
github.com/cch123/httprouter.(*node).insertChild(0xc4200801e0, 0xc42004fc01, 0x126b177, 0x3, 0x126b171, 0x9, 0x127b668)
  /Users/caochunhui/go_work/src/github.com/cch123/httprouter/tree.go:256 +0x841
github.com/cch123/httprouter.(*node).addRoute(0xc4200801e0, 0x126b171, 0x9, 0x127b668)
  /Users/caochunhui/go_work/src/github.com/cch123/httprouter/tree.go:221 +0x22a
github.com/cch123/httprouter.(*Router).Handle(0xc42004ff38, 0x126a39b, 0x3, 0x126b171, 0x9, 0x127b668)
  /Users/caochunhui/go_work/src/github.com/cch123/httprouter/router.go:262 +0xc3
github.com/cch123/httprouter.(*Router).GET(0xc42004ff38, 0x126b171, 0x9, 0x127b668)
  /Users/caochunhui/go_work/src/github.com/cch123/httprouter/router.go:193 +0x5e
main.main()
  /Users/caochunhui/test/go_web/httprouter_learn2.go:18 +0xaf
exit status 2
</code></pre>
<p>还有一点需要注意，因为 httprouter 考虑到字典树的深度，在初始化时会对参数的数量进行限制，所以在路由中的参数数目不能超过 255，否则会导致 httprouter 无法识别后续的参数。不过这一点上也不用考虑太多，毕竟 URI 是人设计且给人来看的，相信没有长得夸张的 URI 能在一条路径中带有 200 个以上的参数。</p>
<p>除支持路径中的 wildcard 参数之外，httprouter 还可以支持 <code>*</code> 号来进行通配，不过 <code>*</code> 号开头的参数只能放在路由的结尾，例如下面这样：</p>
<pre><code class="language-shell">Pattern: /src/*filepath

 /src/                     filepath = &quot;&quot;
 /src/somefile.go          filepath = &quot;somefile.go&quot;
 /src/subdir/somefile.go   filepath = &quot;subdir/somefile.go&quot;
</code></pre>
<p>这种设计在 RESTful 中可能不太常见，主要是为了能够使用 httprouter 来做简单的 HTTP 静态文件服务器。</p>
<p>除了正常情况下的路由支持，httprouter 也支持对一些特殊情况下的回调函数进行定制，例如 404 的时候：</p>
<pre><code class="language-go">r := httprouter.New()
r.NotFound = http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
	w.Write([]byte(&quot;oh no, not found&quot;))
})
</code></pre>
<p>或者内部 panic 的时候：</p>
<pre><code class="language-go">r.PanicHandler = func(w http.ResponseWriter, r *http.Request, c interface{}) {
	log.Printf(&quot;Recovering from panic, Reason: %#v&quot;, c.(error))
	w.WriteHeader(http.StatusInternalServerError)
	w.Write([]byte(c.(error).Error()))
}
</code></pre>
<p>目前开源界最为流行（star 数最多）的 Web 框架 <a href="https://github.com/gin-gonic/gin">gin</a> 使用的就是 httprouter 的变种。</p>
<h2>5.2.2 原理</h2>
<p>httprouter 和众多衍生 router 使用的数据结构被称为压缩字典树（Radix Tree）。读者可能没有接触过压缩字典树，但对字典树（Trie Tree）应该有所耳闻。<em>图 5-1</em> 是一个典型的字典树结构：</p>
<p><img src="../images/ch6-02-trie.png" alt="trie tree"></p>
<p><em>图 5-1 字典树</em></p>
<p>字典树常用来进行字符串检索，例如用给定的字符串序列建立字典树。对于目标字符串，只要从根节点开始深度优先搜索，即可判断出该字符串是否曾经出现过，时间复杂度为 <code>O(n)</code>，n 可以认为是目标字符串的长度。为什么要这样做？字符串本身不像数值类型可以进行数值比较，两个字符串对比的时间复杂度取决于字符串长度。如果不用字典树来完成上述功能，要对历史字符串进行排序，再利用二分查找之类的算法去搜索，时间复杂度只高不低。可认为字典树是一种空间换时间的典型做法。</p>
<p>普通的字典树有一个比较明显的缺点，就是每个字母都需要建立一个孩子节点，这样会导致字典树的层数比较深，压缩字典树相对好地平衡了字典树的优点和缺点。是典型的压缩字典树结构：</p>
<p><img src="../images/ch6-02-radix.png" alt="radix tree"></p>
<p><em>图 5-2 压缩字典树</em></p>
<p>每个节点上不只存储一个字母了，这也是压缩字典树中 “压缩” 的主要含义。使用压缩字典树可以减少树的层数，同时因为每个节点上数据存储也比通常的字典树要多，所以程序的局部性较好（一个节点的 path 加载到 cache 即可进行多个字符的对比），从而对 CPU 缓存友好。</p>
<h2>5.2.3 压缩字典树创建过程</h2>
<p>我们来跟踪一下 httprouter 中，一个典型的压缩字典树的创建过程，路由设定如下：</p>
<pre><code>PUT /user/installations/:installation_id/repositories/:repository_id

GET /marketplace_listing/plans/
GET /marketplace_listing/plans/:id/accounts
GET /search
GET /status
GET /support

补充路由：
GET /marketplace_listing/plans/ohyes
</code></pre>
<p>最后一条补充路由是我们臆想的，除此之外所有 API 路由均来自于 <code>api.github.com</code>。</p>
<h3>5.2.3.1 root 节点创建</h3>
<p>httprouter 的 Router 结构体中存储压缩字典树使用的是下述数据结构：</p>
<pre><code class="language-go">// 略去了其它部分的 Router struct
type Router struct {
	// ...
	trees map[string]*node
	// ...
}
</code></pre>
<p><code>trees</code> 中的 <code>key</code> 即为 HTTP 1.1 的 RFC 中定义的各种方法，具体有：</p>
<pre><code class="language-shell">GET
HEAD
OPTIONS
POST
PUT
PATCH
DELETE
</code></pre>
<p>每一种方法对应的都是一棵独立的压缩字典树，这些树彼此之间不共享数据。具体到我们上面用到的路由，<code>PUT</code> 和 <code>GET</code> 是两棵树而非一棵。</p>
<p>简单来讲，某个方法第一次插入的路由就会导致对应字典树的根节点被创建，我们按顺序，先是一个 <code>PUT</code>：</p>
<pre><code class="language-go">r := httprouter.New()
r.PUT(&quot;/user/installations/:installation_id/repositories/:reposit&quot;, Hello)
</code></pre>
<p>这样 <code>PUT</code> 对应的根节点就会被创建出来。把这棵 <code>PUT</code> 的树画出来：</p>
<p><img src="../images/ch6-02-radix-put.png" alt="put radix tree"></p>
<p><em>图 5-3 插入路由之后的压缩字典树</em></p>
<p>radix 的节点类型为 <code>*httprouter.node</code>，为了说明方便，我们留下了目前关心的几个字段：</p>
<pre><code>path: 当前节点对应的路径中的字符串

wildChild: 子节点是否为参数节点，即 wildcard node，或者说 :id 这种类型的节点

nType: 当前节点类型，有四个枚举值: 分别为 static/root/param/catchAll。
    static                   // 非根节点的普通字符串节点
    root                     // 根节点
    param                    // 参数节点，例如 :id
    catchAll                 // 通配符节点，例如 *anyway

indices：子节点索引，当子节点为非参数类型，即本节点的 wildChild 为 false 时，会将每个子节点的首字母放在该索引数组。说是数组，实际上是个 string。

</code></pre>
<p>当然，<code>PUT</code> 路由只有唯一的一条路径。接下来，我们以后续的多条 GET 路径为例，讲解子节点的插入过程。</p>
<h3>5.2.3.2 子节点插入</h3>
<p>当插入 <code>GET /marketplace_listing/plans</code> 时，类似前面 PUT 的过程，GET 树的结构如 <em>图 5-4</em>：</p>
<p><img src="../images/ch6-02-radix-get-1.png" alt="get radix step 1"></p>
<p><em>图 5-4 插入第一个节点的压缩字典树</em></p>
<p>因为第一个路由没有参数，path 都被存储到根节点上了。所以只有一个节点。</p>
<p>然后插入 <code>GET /marketplace_listing/plans/:id/accounts</code>，新的路径与之前的路径有共同的前缀，且可以直接在之前叶子节点后进行插入，那么结果也很简单，插入后的树结构见 <em>图 5-5</em>:</p>
<p><img src="../images/ch6-02-radix-get-2.png" alt="get radix step 2"></p>
<p><em>图 5-5 插入第二个节点的压缩字典树</em></p>
<p>由于 <code>:id</code> 这个节点只有一个字符串的普通子节点，所以 indices 还依然不需要处理。</p>
<p>上面这种情况比较简单，新的路由可以直接作为原路由的子节点进行插入。实际情况不会这么美好。</p>
<h3>5.2.3.3 边分裂</h3>
<p>接下来我们插入 <code>GET /search</code>，这时会导致树的边分裂，见 <em>图 5-6</em>。</p>
<p><img src="../images/ch6-02-radix-get-3.png" alt="get radix step 3"></p>
<p><em>图 5-6 插入第三个节点，导致边分裂</em></p>
<p>原有路径和新的路径在初始的 <code>/</code> 位置发生分裂，这样需要把原有的 root 节点内容下移，再将新路由 <code>search</code> 同样作为子节点挂在 root 节点之下。这时候因为子节点出现多个，root 节点的 indices 提供子节点索引，这时候该字段就需要派上用场了。&quot;ms&quot; 代表子节点的首字母分别为 m（marketplace）和 s（search）。</p>
<p>我们一口作气，把 <code>GET /status</code> 和 <code>GET /support</code> 也插入到树中。这时候会导致在 <code>search</code> 节点上再次发生分裂，最终结果见 <em>图 5-7</em>：</p>
<p><img src="../images/ch6-02-radix-get-4.png" alt="get radix step 4"></p>
<p><em>图 5-7 插入所有路由后的压缩字典树</em></p>
<h3>5.2.3.4 子节点冲突处理</h3>
<p>在路由本身只有字符串的情况下，不会发生任何冲突。只有当路由中含有 wildcard（类似 :id）或者 catchAll 的情况下才可能冲突。这一点在前面已经提到了。</p>
<p>子节点的冲突处理很简单，分几种情况：</p>
<ol>
<li>在插入 wildcard 节点时，父节点的 children 数组非空且 wildChild 被设置为 false。例如：<code>GET /user/getAll</code> 和 <code>GET /user/:id/getAddr</code>，或者 <code>GET /user/*aaa</code> 和 <code>GET /user/:id</code>。</li>
<li>在插入 wildcard 节点时，父节点的 children 数组非空且 wildChild 被设置为 true，但该父节点的 wildcard 子节点要插入的 wildcard 名字不一样。例如：<code>GET /user/:id/info</code> 和 <code>GET /user/:name/info</code>。</li>
<li>在插入 catchAll 节点时，父节点的 children 非空。例如：<code>GET /src/abc</code> 和 <code>GET /src/*filename</code>，或者 <code>GET /src/:id</code> 和 <code>GET /src/*filename</code>。</li>
<li>在插入 static 节点时，父节点的 wildChild 字段被设置为 true。</li>
<li>在插入 static 节点时，父节点的 children 非空，且子节点 nType 为 catchAll。</li>
</ol>
<p>只要发生冲突，都会在初始化的时候 panic。例如，在插入我们臆想的路由 <code>GET /marketplace_listing/plans/ohyes</code> 时，出现第 4 种冲突情况：它的父节点 <code>marketplace_listing/plans/</code> 的 wildChild 字段为 true。</p>


                        <hr><table><tr><td><img width="222px" src="https://chai2010.cn/advanced-go-programming-book/css.png"></td><td><img width="222px" src="https://chai2010.cn/advanced-go-programming-book/cch.png"></td></tr></table>

                        
                            <div id="giscus-container"></div>
                        

                        
                            <footer class="page-footer">
                                <span>© 2019-2022 | <a href="https://github.com/chai2010/advanced-go-programming-book">柴树杉、曹春晖</a> 保留所有权利</span>
                            </footer>
                        
                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                        
                            <a rel="prev" href="../ch5-web\ch5-01-introduction.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>
                        
                        
                            <!-- ../ch5-web\ch5-03-middleware.html -->
                            <a rel="next" href="../ch5-web\ch5-03-middleware.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>
                        
                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                
                    <a rel="prev" href="../ch5-web\ch5-01-introduction.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>
                
                
                    <a rel="next" href="../ch5-web\ch5-03-middleware.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
                
            </nav>

        </div>

        <script type="text/javascript">
            window.playground_copyable = true;
        </script>
        <script src="../static/wabook/mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../static/wabook/clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../static/wabook/highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="../static/wabook/book.js" type="text/javascript" charset="utf-8"></script>
        
        <script type="text/javascript" charset="utf-8">
            var pagePath = "ch5-web\ch5-02-router.md"
        </script>

        <!-- Custom JS scripts -->
        
            <script src="../static/wabook/giscus.js" type="text/javascript" charset="utf-8"></script>
        

    </body>
</html>
